Graphs typically include multiple nodes or vertices connected to one another by one or more edges. Graphs may be directed or undirected, and may have a weight, a length, or a cost associated with one or more of the edges. Graphs are useful for modeling many real world systems such as the World Wide Web and transportation systems such as highways. One frequently performed operation on a graph is the computation of the shortest distance between two nodes of the graph. For example, in a graph representing a highway system, a user may request the shortest distance between their house and their destination before embarking on a trip. Accordingly, the user may use the graph to determine the shortest distance.
Existing methods for computing the shortest distance in a graph between two nodes include Dijkstra's algorithm and the A* search algorithm. However, these methods have several drawbacks. For example, as the number of nodes and edges in a graph grows, the time and computing resources needed by these methods to calculate the shortest distance may become burdensome. Users have become accustomed to near instantaneous results from computing applications, making such time and resource requirements unacceptable.